第5.1节 K近邻思想与原理
各位朋友大家好，欢迎来到月来客栈，我是掌柜空字符。
本期推送内容目录如下，如果你觉得本期内容对你所有帮助欢迎点个赞、关个注、下回更新不迷路。
5.1 k近邻思想 5.2 k近邻原理 5.2.1 算法原理 5.2.2 值选择 5.2.3 距离度量
在前几章中，笔者分别介绍了线性回归、逻辑回归及模型的改善与泛化。从这章开始，我们将继续学习下一个新的算法模型——K近邻(K-Nearest Neighbor, KNN)。什么是K近邻呢?
5.1 近邻思想
某一天，你和几位朋友准备去外面聚餐，但是就晚上吃什么菜一直各持己见。最后，无奈的你提出用少数人服从多数人的原则进行选择。于是你们每个人都将自己想要吃的东西写在了纸条上，最后的统计情况是： 3个人赞成吃火锅、2个人赞成吃炒菜、1个人赞成吃自助。当然，最后你们一致同意按照多数人的意见去吃了火锅。那这个吃火锅和K近邻有什么关系呢？吃火锅确实跟K近邻没关系，但是整个决策的过程却完全体现了近邻算法的决策过程。
5.2 近邻原理
5.2.1 算法原理
如图5-1所示，黑色样本点为原始的训练数据，并且包含了0、1、2这3个类别（分别为图中不同形状的样本点）。现在得到一个新的样本点（图中黑色倒三角），需要对其所属类别进行分类。近邻是如何对其进行分类的呢？
首先近邻会确定一个值，然后选择离自己（黑色倒三角样本点）最近的个样本点，最后根据投票的规则（Majority Voting Rule）确定新样本所属的类别。如图5-1所示，示例中选择了离三角形样本点最近的14个样本点（正方形4个、圆形7个、星形3个），并且在图中，离三角形样本点最近的14个样本中最多的为圆形样本，所以近邻算法将把新样本归类为类别1。
因此，对于近邻算法的原理可以总结为如下3个步骤：
1. 确定一个值
用于选择离自己（三角形样本点）最近的样本数。
2. 选择一种度量距离
用来计算并得到离自己最近的个样本，示例中采用了应用最为广泛的欧氏距离。
3. 确定一种决策规则
用来判定新样本所属类别，示例中采用了基于投票的分类规则。
可以看出，近邻分类的3个步骤其实对应了3个超参数的选择，但是，通常来讲，对于决策规则的选择基本上采用了基于投票的分类规则，因此下面对于这个问题也就不再进行额外讨论了。
5.2.2 值选择
值的选择会极大程度上影响近邻的分类结果。如图5-2所示，可以想象，如果在分类过程中选择较小的值，则会使模型的训练误差减小从而使模型的泛化误差增大，也就是模型过于复杂而产生了过拟合现象。当选择较大的值时，将使模型趋于简单，容易发生欠拟合的情况。极端情况下，如果直接将值设置为样本总数，则无论新输入的样本点位于什么地方，模型都会简单地将它预测为训练样本最多的类别，并且恒定不变，因此，对于值的选择，依然建议使用第4章所介绍的交叉验证方法进行选择。
5.2.3 距离度量
在样本空间中，任意两个样本点之间的距离都可以看作两个样本点之间相似性的度量。两个样本点之间的距离越近，也就意味着这两个样本点越相似。在第10章介绍聚类算法时，同样也会用到样本点间相似性的度量。同时，不同的距离度量方式将会产生不同的距离，进而最后产生不同的分类结果。虽然一般情况下近邻使用的是欧氏距离，但也可以是其他距离，例如更一般的距离或者Minkowski距离[1]。